//
//  Matrix.cpp
//  cpp
//
//  Created by xueshan1 on 2019/9/6.
//  Copyright © 2019 xueshan1. All rights reserved.
//

#include <stdio.h>
#include <string>
#include <vector>
#include <queue>

using namespace std;
using std :: vector;

//矩阵 (二维数组)

#pragma mark - 1.搜索二维矩阵
//写出一个高效的算法来搜索 m × n矩阵中的值。
//这个矩阵具有以下特性：
//  每行中的整数从左到右是排序的。
//  每行的第一个数大于上一行的最后一个整数。
bool searchMatrix(vector<vector<int>> arr, int target){
    //思路:从左下角-> 右上角, 缩小范围
    long row = arr.size() - 1;
    long col = 0;
    
    while (row>=0 && col<arr[0].size()) {
        if (arr[row][col] == target) {
            return true;
        }else if (arr[row][col] < target){
            col++;
        }else{
            row--;
        }
        
    }
    
    return false;
}

#pragma mark - 2.矩阵旋转
//给定一个N×N的二维矩阵表示图像,90度顺时针旋转图像
//1.双层for 循环,加入到新的数组中
//2.原地旋转 两个for循环,外层for控制层数, 内层for将每一层都进行旋转(每次交换n(维)个点)
//https://gitee.com/code136585331/codes/f92lqcz4e1bhrx6atgpkm12
// https://blog.csdn.net/qq_43109561/article/details/88778167

#pragma mark - 3.最小路径和
//给定一个只含非负整数的m*n网格，找到一条从左上角到右下角的可以使数字和最小的路径。
//https://www.baidu.com/s?ie=UTF-8&wd=%E6%9C%80%E5%B0%8F%E8%B7%AF%E5%BE%84%E5%92%8C
//思路:维护一个二位数组,每一个点 等于 到当前点的最小路径和
int minPathSum(vector<vector<int>> grid){
    long row = grid.size();
    long col = grid[0].size();
    vector<vector<int>> dp(0);
    //第一个点
    dp[0][0] = grid[0][0];
    //填充 第一行
    for (int i = 1 ; i<col; i++) {
        dp[0][i] = grid[0][i] + dp[0][i-1];
    }
    //填充 第一列
    for (int j = 1; j< row; j++) {
        dp[j][0] = grid[j][0] + dp[j-1][0];
    }
    //填充 其他点
    for (int i = 1; i<row; i++) {
        for (int j = 1 ; j<col; j++) {
            dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]); //选择一个小的, 加上当前点 = 到当前点的路径和
        }
    }
    
    return dp[row-1][col-1];//最后的点, 就是最小的和了
}


